#include <iostream>
using namespace std;
// 剑指offer 22.链表中倒数第k个结点
// 输入一个链表，输出该链表中倒数第k个结点
// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* slow, *fast;
        slow = fast = head;
        while(fast != nullptr && k-- > 0) {
            fast = fast->next;
        }
        if(fast == nullptr)
            return nullptr;
        while(fast != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};
int main() {
    // 给定链表 1->2->3->4->5 和 k = 2，返回链表 4->5
    ListNode* head1 = nullptr, *pre = nullptr;
    for(int i = 1; i <= 5; i++) {
        ListNode* curr = new ListNode(i);
        if(head1 == nullptr) {
            head1 = curr;
            pre = curr;
        } else {
            pre->next = curr;
            pre = pre->next;
        }
    }
    ListNode* newNode = Solution().getKthFromEnd(head1,2);

    return 0;
}
